package medium;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/*
15. 三数之和
解题思路：双指针
 */
public class LeeCode15 {

  public static void main(String[] args) {
    List<List<Integer>> sum = new LeeCode15().threeSum(new int[]{-1, 0, 1, 2, -1, -4});
  }

  public List<List<Integer>> threeSum(int[] nums){
    List<List<Integer>> res = new ArrayList();
    if (nums.length == 0 || nums.length < 3) return res;
    Arrays.sort(nums);
    for (int i = 0; i < nums.length; i++) {
      if (nums[i] > 0) break;//第一个数就大于0，则三数一定大于0
      if(i > 0 && nums[i] == nums[i-1]) continue;//去重
      int l = i + 1;
      int r = nums.length - 1;
      while (l < r){
        int sum = nums[i] + nums[l] + nums[r];
        if (sum == 0){
          res.add(Arrays.asList(nums[i],nums[l],nums[r]));
          while (l < r && nums[l] == nums[l + 1]) l++; // 去重
          while (l < r && nums[r] == nums[r - 1]) r--; // 去重
          l++;
          r--;
        }else if (sum < 0){
          l++;
        }else if (sum > 0){
          r--;
        }
      }
    }
    return res;
  }
}
